package com.mamingchao.basic.manacher;


import org.springframework.util.ObjectUtils;

import java.util.Arrays;
import java.util.Objects;

/**
 * Created by mamingchao on 2024/12/4.
 */
public class Manacher {

    /**
     *  本方法主要负责把 字符串，每隔一个字符，都插入一个分隔符，比如#
     *  其实，放入什么分隔符，都不影响结果计算；因为计算回文半径的时候
     *  只是 插入的分隔符和和分隔符对比 是不是相同； 原本的串里的字符相互判断
     *  不存在 插入的分隔符和原本的串里的字符相互判断的情况
     * @param s 待插入分隔符到字段的，待处理字符串， 例如：abckcbt
     * @return 每隔一个字符都插入了分隔符的字符串，例如：#a#b#c#k#c#b#t#
     */
    private static String insertSeperatorToStr(String s){
        if (Objects.isNull(s) || s.length() ==0)
            return "";

        StringBuffer sb = new StringBuffer("#");
        char[] charArr = s.toCharArray();

        for (int i = 0; i < charArr.length; i++) {
            sb.append(charArr[i]);
            sb.append("#");
        }


        return sb.toString();
    }

    /**
     * @param strWithSeperator 计算带有分隔符的字符串，每个字符回文直径
     * @return 带有分隔符的字符串，每个字符回文直径的数组；
     */
    private static int[] getPalindromeRedius(String strWithSeperator){
        if (Objects.isNull(strWithSeperator) || strWithSeperator.length() ==0)
            return null;

        char[] charArr = strWithSeperator.toCharArray();
        int[] palindromeRediusArr = new int[charArr.length];
        // 最大回文直径的最右侧 index索引位置
        int R = -1;
        // 最大回文直径的中间轴 的index位置
        int C = -1;
        // 相当于i`
        int j = -1;
        // 与R相对的，最大回文直径的最左侧 index索引位置
        int L = -1;

        for (int i = 0; i < charArr.length; i++) {
            if (i>=R) {
                // 要扩R
                expandR(charArr, palindromeRediusArr, R, C, i);
            } else {
                j = 2*C -i;
                L = 2*C -R;
                if (j>L){ // i的回文直径 跟i`的回文直径相同
                    palindromeRediusArr[i] = palindromeRediusArr[j];
                }else if (j<L){ 
                    palindromeRediusArr[i] = 2*(R-i) +1;
                }else{ // j == L
                    // 要扩R
                    expandR(charArr, palindromeRediusArr, R, C, i);
                }
            }
        }

        return palindromeRediusArr;
    }

    private static void expandR(char[] charArr, int[] palindromeRediusArr, int R, int C, int i){

        // 基于i，扩容的幅度
        int j= 0;


        while ((i-j)>=-1 && (i+j) <=palindromeRediusArr.length && i < palindromeRediusArr.length) {
            // 扩出边界的时候，停止扩，结算
            if ((i-j)==-1 || (i+j) ==palindromeRediusArr.length) {
                palindromeRediusArr[i] = 2*(j-1) + 1;
                j = 0;
                i++;
                R = Math.max(i,R);
                C = i;
            } else if (charArr[i-j] == charArr[i+j]) { // 两边相等，继续扩
                R =  Math.max(i+j,R);
                C = i ;
                j ++;
            } else {//两边不再相等，停止扩，结算
                palindromeRediusArr[i] = 2*(j-1) + 1;
                j = 0;
                i++;
                R = Math.max(i,R);
                C = i;
            }
        }



    }

    /**
     * @param palindromeRediusArrWithSeperator 带有分隔符的字符串，每个字符回文直径数组
     * @return 去掉数组中分隔符的回文直径值，只留下原始字符串中各个字符的回文直径值
     */
    private static int[] removeSeperatorToStr(int[] palindromeRediusArrWithSeperator){
        if (!ObjectUtils.isEmpty(palindromeRediusArrWithSeperator)
                || palindromeRediusArrWithSeperator.length==0)
            return null;

        Double size = Math.ceil(palindromeRediusArrWithSeperator.length/2);
        int[] palindromeRediusArrWithoutSeperator = new int[size.intValue()];

        int j = 0 ;
        for (int i = 0; i < palindromeRediusArrWithSeperator.length; i++) {
            // 在加了分隔符的串中，index为奇数的，均为原始串中的字符
            if (i%2 ==1){
                Double palindromeRedius = Math.ceil(palindromeRediusArrWithSeperator[i]/2);
                palindromeRediusArrWithoutSeperator[j++] = palindromeRedius.intValue();
            }
        }

       return palindromeRediusArrWithoutSeperator;
    }

    public static void main(String[] args) {
        final String giveMeATry = "abcbakskabcba";
        String giveMeATryAgain = insertSeperatorToStr(giveMeATry);
        int[] palindromeRediusArr = getPalindromeRedius(giveMeATryAgain);
        System.out.println(Arrays.toString(palindromeRediusArr));
        int[] palindromeRediusArrWithoutSeperator = removeSeperatorToStr(palindromeRediusArr);

        System.out.println(Arrays.toString(palindromeRediusArrWithoutSeperator));
    }

}
